package collection;

/**
 * LinkedList
 */
public class LinkedList01 {

    public static void main(String[] args) {

        /*
            1)LinkedList底层实现了双向链表和双端队列的特点
            2)可以添加任意元素(元素可以重复)，包括null
            3)线程不安全，没有实现同步
         */

        /*
            1)LinkedList 底层维护了一个双向链表
            2)LinkedList 中维护了两个属性 first 和 last 分别指向 首节点 和 尾节点
            3)每个节点(Node对象)，里面又维护了 prev next item 三个属性，其中通过 prev指向前一个
              通过 next 指向后一个。最终实现双向链表
            4)LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高
         */

        //模拟一个简单的双向链表

        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node lmy = new Node("lmy");

        //连接三个结点，形成双向链表
        //jack -> tom -> lmy
        jack.next = tom;
        tom.next = lmy;

        lmy.pre = tom;
        tom.pre = jack;

        //头节点 jack
        Node first = jack;
        //尾节点 lmy
        Node last = lmy;

        //遍历
        System.out.println("====从头到尾遍历双向链表====");

        while(true) {
            if (first == null) {
                break;
            }
            //输出 first 信息
            System.out.println(first);
            first = first.next;
        }

        System.out.println("====从尾到头遍历双向链表====");

        while(true) {
            if (last == null) {
                break;
            }
            //输出 first 信息
            System.out.println(last);
            last = last.pre;
        }

        //链表的添加对象/数据很方便
        //先创建一个Node结点，name = smith
        Node smith = new Node("smith");
        //连接tom smith lmy，就是将smith加入双向链表
        smith.next = lmy;
        smith.pre = tom;
        lmy.pre = smith;
        tom.next = smith;
        //让first再次指向jack
        first = jack;

        System.out.println("====添加smith后从头到尾遍历双向链表====");

        while(true) {
            if (first == null) {
                break;
            }
            //输出 first 信息
            System.out.println(first);
            first = first.next;
        }
    }
}

//定义一个Node类，Node对象表示双向链表的一个结点
class Node{
    public Object item;//真正存放数据

    public Node next;//指向后一个结点

    public Node pre;//指向前一个结点

    public Node(Object name){
        this.item = name;
    }
    public String toString(){
        return "Nodename=" + item;

    }
}